#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣322. 零钱兑换
// 【难度】中等
// 【提交】2024.3.24 https://leetcode.cn/problems/coin-change/submissions/515820318/
// 【标签】动态规划；01背包
class Solution_LC0322 {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        vector<int> dp(amount + 1, 0);
        for (int i = 0; i < amount; ++i) {
            if (i == 0 || dp[i] > 0) { // 细节1：dp[i]==0表示没有任何方法可以凑出面额i，这时计算就要跳过
                for (int c: coins) {
                    if (c <= amount - i) { // 细节2：当心数组越界
                        int a = i + c; // 当前新的面额
                        int cnt = dp[i] + 1; // 组成面额a所需的硬币数
                        if (dp[a] == 0 || dp[a] > cnt) 
                            dp[a] = cnt;
                    }
                }
            }
        }
        return dp[amount] == 0 ? -1 : dp[amount]; // 留意题目要求
    }
};

/**
 * @brief 学习总结：
 * “BFS-松弛”写法在逻辑上正确且常数小，但“0 歧义”降低了可读性与可维护性；改用经典完全背包或 0-1 BFS 模板能让代码更健壮、更易扩展。
优化：经典完全背包写法（更短、更清晰）  
```cpp
int coinChange(vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, LLONG_MAX);
    dp[0] = 0;
    for (int c : coins)
        for (int i = c; i <= amount; ++i)
            if (dp[i - c] != LLONG_MAX)
                dp[i] = min(dp[i], dp[i - c] + 1);
    return dp[amount] == LLONG_MAX ? -1 : dp[amount];
}
```
 */


/* --------------------------------------------------------------------------------------------------------------*
（注：以下内容仅演示如何利用AI工具进行学习和改进，同学们提交时只需要提交上面部分的内容，“学习总结”部分内容可以用AI工具生成）

prompt:
以下是我的代码，请为我生成学习笔记，包括题解和代码注释，并分析总结我的代码，指出优缺点以及改进建议：
```cpp
(源代码，略)
```

学习笔记：LeetCode 322「零钱兑换」  
（提交记录：2024-03-24，C++，用时 12 ms，内存 9.1 MB）

一、题意与模型  
给定不同面额 coins[] 和目标 amount，求组成 amount 所需的最少硬币数。  
硬币可无限使用 → 完全背包（Unbounded Knapsack）。  
若无解，返回 -1。

二、标准 DP 状态设计  
设 dp[i] 表示组成面额 i 所需的最少硬币数。  
初始化：dp[0]=0，其余 dp[i]=∞（或用一个不可能的值标记“不可达”）。  
转移：  
    dp[i] = min(dp[i], dp[i-c]+1)  对所有 c∈coins 且 i≥c  
答案：dp[amount] 若仍为 ∞ 则返回 -1。

三、你的实现思路  
1. 把“从 0 开始 BFS”的思想写成了“类 Dijkstra”的松弛：  
   外层循环按面额 i 从小到大扫描；  
   只有 dp[i]>0（或 i==0）时才用它去更新 i+c。  
2. 用 0 表示“不可达”，因此需要额外判断 dp[i]==0 就跳过。  
3. 最终若 dp[amount]==0 则返回 -1。

四、逐行注释（带细节提醒）
```cpp
class Solution_LC0322 {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        vector<int> dp(amount + 1, 0);   // 0 既当“未访问”又当“不可达”，需要小心
        for (int i = 0; i < amount; ++i) {        // 扫描所有已求出的面额
            if (i == 0 || dp[i] > 0) {            // 只有可达状态才扩展
                for (int c: coins) {
                    if (c <= amount - i) {        // 防越界
                        int a = i + c;
                        int cnt = dp[i] + 1;
                        if (dp[a] == 0 || dp[a] > cnt)
                            dp[a] = cnt;          // 松弛
                    }
                }
            }
        }
        return dp[amount] == 0 ? -1 : dp[amount];
    }
};
```

五、正确性证明  
由于 coins 均为正，i 单调递增，每个状态 i 只会被松弛一次，因此算法等价于 0-1 BFS（边权为 1），必能求出最短路。

六、复杂度  
时间：O(amount·|coins|)  
空间：O(amount)

七、优缺点分析  
优点  
- 思路直观，利用“0 表示未访问”节省一次初始化 ∞ 的开销。  
- 常数较小，实际跑在 12 ms。

缺点 / 潜在隐患  
1. 语义混乱：0 既是“初始值”又是“不可达”标志，阅读成本高，易出错。  
2. 对 amount=0 的特判与循环内“i==0”判断重复。  
3. 外层 for 循环到 amount-1，而内层再+c 可能正好等于 amount，虽然正确，但写法不够简洁。  
4. 没有提前剪枝：若 coins 中有 1，可直接返回 amount；若最小硬币 >1 且 amount 很大，可做模运算或数学剪枝。  
5. 无法直接推广到“恰好装满”且要求“方案数”或“字典序最小方案”等扩展问题。

八、改进建议  
1. 经典完全背包写法（更短、更清晰）  
```cpp
int coinChange(vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, LLONG_MAX);
    dp[0] = 0;
    for (int c : coins)
        for (int i = c; i <= amount; ++i)
            if (dp[i - c] != LLONG_MAX)
                dp[i] = min(dp[i], dp[i - c] + 1);
    return dp[amount] == LLONG_MAX ? -1 : dp[amount];
}
```
2. 若 coins 数组较大且 amount 很大，可：  
   - 先排序，用单调队列优化完全背包（O(amount))；  
   - 或采用“BFS 最短路”版本（仅当边权为 1 时更快）。  
3. 提前特判：  
   if (amount == 0) return 0;  
   if (coins.empty()) return -1;  
   int minC = *min_element(coins.begin(), coins.end());  
   if (minC > amount) return -1;  
4. 若面试/竞赛场景，建议用 ∞=0x3f3f3f3f（int）或 LLONG_MAX（long long），避免 0/1 歧义。  
5. 若需要输出具体方案，可额外记录前驱 coin 索引，最后回溯。

九、一句话总结  
你的“BFS-松弛”写法在逻辑上正确且常数小，但“0 歧义”降低了可读性与可维护性；改用经典完全背包或 0-1 BFS 模板能让代码更健壮、更易扩展。
* 
 * 
 */